﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 原题连接：https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&ru=/exam/oj

/*
题目描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：
𝑛
≤
1000
n≤1000
要求：空间复杂度
𝑂
(
1
)
O(1)，时间复杂度
𝑂
(
𝑛
)
O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1
输入：
{1,2,3},{4,5},{6,7}
复制
返回值：
{6,7}
复制
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入：
{1},{2,3},{}
复制
返回值：
{}
复制
说明：
2个链表没有公共节点 ,返回null，后台打印{}
*/



struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
// 开始解题：
// 方法——利用等量关系
class Solution {
public:
	// 核心思想：设两个链表不想交部分的长度分别为x1、x2，相交部分长度为x
	// 则有x1 + x + x2 = x2 + x + x1
	// 以上等式的含义为：由链表1的起点走到结尾再转到链表2的起点走完链表2的不相交部分的长度
	// 和
	// 由链表2的起点走到结尾再转到链表1的起点走完链表1的不相交部分的长度
	// 两者路程是相同的，所以照这样走下去，两者最终会在第一次相交的节点处相遇
	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
		ListNode* cur1 = pHead1;
		ListNode* cur2 = pHead2;
		while (cur1 != cur2) {
			if (cur1) {
				cur1 = cur1->next;
			}
			else {
				cur1 = pHead2;
			}
			if (cur2) {
				cur2 = cur2->next;
			}
			else {
				cur2 = pHead1;
			}
		}
		return cur1;
	}
};
